LeetCode-24-Swap Nodes in Pairs

Posted by 刘知安 on 2019-03-13
文章目录
  1. 题目
  2. 示例:
    1. 坑点&思路

题目

给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

说明:

- 你的算法只能使用常数的额外空间。
- 你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

坑点&思路

一开始理解错了,也没仔细看题目,两两交换,那不就是直接像冒泡一样,那么结果就是最前一个结点变到最后去。。。too yong too simple.(题目中文翻译的就是有点说不明白的感觉)

原来题目的意思是每两个相邻结点换一次,这个其实也很容易做到,就是把要交换的两个结点的next域变动一下,注意下交换顺序就可以,大概是下面这样的交换方式:

最开始是如下情况。
在这里插入图片描述
一旦n1.next 和 n1.next.next不是空,也就是说存在两个可以交换的结点,那么就交换并后移,like this:

1
2
3
4
5
6
7
#  do swap
n1.next = n3
n3.next = n2
n2.next = n4

# move pointer
n1 = n2

然后就成了这样:
在这里插入图片描述
然后就一直这样做下去就完事儿了。

不过要注意,我们思考的时候可以先给它标出n1、n2、n3、n4,写代码的时候一定要先判断它们都不为空,再进行变量赋值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None


class Solution:
def swapPairs(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
# 链表为空或者只有一个结点
if head is None or head.next is None:
return head

# n1初始化在头指针之前
newList = ListNode(-1)
newList.next = head
n1 = newList
# 当存在两个相邻结点可以交换
while n1.next is not None and n1.next.next is not None:
n2 = n1.next
n3 = n2.next
n4 = n3.next

# do swap
n1.next = n3
n3.next = n2
n2.next = n4

# move pointer
n1 = n2

return newList.next

if __name__ == '__main__':
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)

s = Solution()
list = s.swapPairs(head)